#define _CRT_SECURE_NO_WARNINGS 1
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

//O(n*log N)
class KthLargestVector {
public:
    KthLargestVector(int k, vector<int>& nums) {
        _k = k;
        for (auto& e : nums)
        {
            _nums.push_back(e);
        }
    }

    int add(int val) {
        _nums.push_back(val);
        sort(_nums.begin(), _nums.end());
        return _nums[_nums.size() - _k];
    }

private:
    vector<int> _nums;
    int _k;
};


//O(log K)
class KthLargestHeap {
public:
    KthLargestHeap(int k, vector<int>& nums) {
        _k = k;
        for (auto& e : nums)
        {
            _pq.push(e);
            if (_pq.size() > k)
            {
                _pq.pop();
            }
        }
    }

    int add(int val) {
        _pq.push(val);
        if (_pq.size() > _k)
        {
            _pq.pop();
        }
        return _pq.top();
    }

private:
    priority_queue<int, vector<int>, greater<int>> _pq;
    int _k;
};